//========================================================//
// Cryptography big integer clasess                       //
// Author: Kozlov Dmitry aka LandFox kozlov@ccfit.nsu.ru  //
// NSU FIT September - October 2004                       //
//========================================================//

#include <stdio.h>
#include "cryptint.h"
#include <string.h>
#include <time.h>

cCryptIntData::cCryptIntData(const char * data, int length,bool ascii) {
	char buf[256];
	int i;

	memset(this->data,0,128);

	if (!data) return;

	if (!ascii) {
		if (length > 128) throw EXC_WrongSize;
		memcpy(this->data,data,length);
	} else {
		memset(buf,0,256);

		for(i = 0; i < length; i++) {
			buf[length - i - 1] = data[i];
		}

		for(i = 0 ; i < length; i ++) {
			if (buf[i] >= '0' && buf[i] <= '9') buf[i] -= '0'; else
				if (buf[i] >= 'a' && buf[i] <= 'f') buf[i] -= 'a' - 10; else
					if (buf[i] >= 'A' && buf[i] <= 'F') buf[i] -= 'A' - 10; else
						throw EXC_WrongCharacter;
		}			

		for(i = 0; i < ((length + 1) >> 1); i ++) {
			(this->data)[i] = (buf[i << 1] | buf[(i << 1)+ 1] << 4);
		}
	}
}

void cCryptIntManager::setMode(const cCryptIntData& mod) {
	int i;
	qword a,alast;
	unsigned long * buf;

	memset(mode + 128,0,128);
	memcpy(mode,mod.data,128);

	for(mode_length = (128 / 4) -1 ; (!((unsigned long *)mode)[mode_length]) && (mode_length >= 0); mode_length --);
	mode_length ++;//length = mode_length

	for(i = 1; i < 32; i ++) if (!(((unsigned long *)mode)[mode_length - 1] >> i)) break;
	shift = 32 - i;

	buf = (unsigned long *)mode;

	alast = 0;
	for(i = 0 ; i < 64; i++) { //shift on this->shift
		a = (qword)buf[i] << shift;
		buf[i] = a | alast;
		alast = a >> 32;
	}
}

void cCryptIntManager::Mode(unsigned char * indata) {//data = data mod c
	unsigned long *r ,* buf , rarr[100] , bufarr[100], data[100];
	qword qguess,preres,carry;
	unsigned long * m = (unsigned long *)mode;
	unsigned long num_length,hidwq,lodwq;
	bool readyResult = false;
	unsigned long a1,aold1;

	buf = (unsigned long *) bufarr;
	r = (unsigned long *) rarr;

	qword a,aold;
	int i,j,k;
	int debug = 1;


	memcpy(data,indata,256);
	memset(r,0,260);//r = 0

	aold = 0;

	if (mode_length > 1) {
		for(i = 0 ; i < 64; i++) { //shift on this->shift
			a = (qword)data[i] << shift;
			data[i] = a | aold;
			aold = a >> 32;
		}
	}

	for(num_length = (256 / 4) - 1; (!((unsigned long *)data)[num_length]) && (num_length >= 0); num_length --);
	num_length ++;//length = mode_length

	if (num_length < mode_length) return;//goto end
	if (mode_length == 1) {
		qword rest = 0;
		for( i = num_length - 1; i >=0 ; i--) {
			rest = ((rest << 32) + data[i]) % (qword)m[0];
		}

		memset(indata,0,256);
		*(unsigned long *)indata = rest >> shift;
		return;
	}

	memcpy(r,((unsigned long *)data) + num_length - mode_length,mode_length << 2);

	for (i = num_length - mode_length - 1; i >= 0 ;i --) {
		for(j = num_length - i; j >= 0; j --) r[j + 1] = r[j];
		r[0] = ((unsigned long *)data)[i];//++

		memset(buf,0,260);//for debug

		if ((!r[mode_length]) && i) continue;//mega compare

		if (!r[mode_length]) {
			qguess = *(qword *)(r + mode_length - 1) / *(qword *)(m + mode_length - 1);
		}	else {

			qguess = (*(qword *)(r + mode_length - 1)) / (qword)m[mode_length - 1];
			qword res = (*(qword *)(r + mode_length - 1)) % (qword)m[mode_length - 1];
			while (res < (((qword)1) << 32)) {
				if (qguess * m[mode_length - 2] > (res << 32) + r[mode_length - 2] || qguess == 0 ) {//q != BASE
					qguess --;
					res += m[mode_length - 1];
				} else break;
			}
		}

		if (qguess >= 1) {
			hidwq = qguess >> 32;
			lodwq = (unsigned long)qguess;

			preres = lodwq * (qword)m[0];
			buf[0] =(unsigned long)preres;
			carry = preres >> 32;

			for(k = 1; k < mode_length + 1; k ++) {
				preres = ((qword)m[k]) * lodwq + ((qword)m[k - 1]) * hidwq + carry;
				buf[k] = (unsigned long)preres;
				carry = preres >> 32;
			}

			buf[k] = carry;
			carry = 0;
			for(k = 0; k < 64; k++) {
				preres = (qword)r[k] - (qword)buf[k] + carry;
				r[k] = (unsigned long)preres;
				carry = ((preres >> 32) << 32) | (preres >> 32);
			}

			if (!carry) readyResult = true;
		}

		if (!readyResult) while(1) {
			carry = 0;
			for(k = 0; k < 64; k++) {
				preres = (qword)r[k] + (qword)m[k] + carry;
				r[k] = (unsigned long)preres;
				carry = preres >> 32;
			}
			if (!r[63]) break;
		}
	}

	if (shift) {
		aold1 = 0;
		for(i = 63 ; i >= 0; i--) {
			a1 = (r[i] >> shift) | aold1;
			aold1 = r[i] << (32 - shift);
			r[i] = a1;
		}
	}

	memcpy(indata,r,256);//256
}

void cCryptIntManager::Mul(cCryptIntData& va , const cCryptIntData& vb) {//a = (a * b) mod c
	unsigned long buf[65];
	const unsigned long *val,*vbl;
	qword a;
	int i,j;

	val = reinterpret_cast<const unsigned long *>(va.data);
	vbl = reinterpret_cast<const unsigned long *>(vb.data);
	memset(buf,0,256);//fill by zero

	for(i = 0 ; i < 32; i ++) {
		a = 0;
		for(j = 0; j < 32; j ++) {
			a += (qword)val[j]*vbl[i] + (qword)buf[i + j];
			buf[i + j] = a;
			a >>= 32;
		}
		buf[i + 32] = a;
	}

	Mode((unsigned char *)buf);
	memcpy(va.data,buf,128);

}

cCryptIntManager::cCryptIntManager() {
	mode = new unsigned char [256];
}

cCryptIntManager::cCryptIntManager(const cCryptIntData& mod) {
	mode = new unsigned char [256];
	setMode(mod);
}

cCryptIntManager::~cCryptIntManager() {
	delete[] mode;
}

void cCryptIntManager::exp(cCryptIntData& x,const cCryptIntData& y) {//x = x^y mod c
	int i,j,bit;
	unsigned long * ly = (unsigned long *)y.data;
	cCryptIntData result(NULL,0,true);

	result.data[0] = 0x01;
	for(i = 0; i < 128 / 4 ; i++) {
		for( j = 0; j < 32 ; j++) {
			bit = (ly[i] >> j) & 0x1L;
			if (bit) {
				Mul(result,x);
			}
			Mul(x,x);
		}
	}

	memcpy(x.data,result.data,128);
}

//#define TEST_MAIN

#ifdef TEST_MAIN
char as[] = "FF673467233246327DFBBC45000DA3FF898923231123123413", bs[] = "234234234FFA2893FCC7FAC004A5892CB10CC5674EE";

const cs[] = "DA9A18547FF03B385CC16508C173A7EF4EB61CB40EF8FEF3B31F145051676166BCDC3FE6B799FC394D08C26385F9413F896E09117E46209D6923602683CEA100924A6EE695281775C619DAA94EA8CB3691B4275B0183F1D39639EBC92995FE645D6C1BC28D409E585549BBD2C5DCDD6C208B04EADD8B7A6D997F72CBAD88390F";

//char as[] = "2" , bs[] = "43",cs[] = "F7CA5D1D52";
char bs1[] = "03"; 

char y[128];
cCryptIntData c(cs,sizeof(cs) - 1,true);
cCryptIntData *a, *b, *b1;
cCryptIntManager vManager(c);

inline long long curtime(void);
long long time1,time2;
clock_t time3,time4;
unsigned char buf[512];
int key_flag;

#define TEST_DEBUG

int main(int argc, char ** argv) {

	srand(time(NULL));
	for(int i = 0; i < 8 ; i ++) y[i] = rand() & 0xff;

	if (argc < 2) {
		printf("To few parametrs.\n");
		return 0;
	}

	if (!strcmp(argv[1],"-1")) key_flag = 1;
	else if (!strcmp(argv[1],"-2")) key_flag = 2;
	else {
		printf("Wrong parametrs.\n");
		return 0;
	}

#ifndef TEST_DEBUG
	a = new cCryptIntData("2",1,true);
	b = new cCryptIntData(y,128);
#else
	a = new cCryptIntData(as,sizeof(as) - 1,true);
	b = new cCryptIntData(bs,sizeof(bs) - 1,true);
	b1 = new cCryptIntData(bs1,sizeof(bs1) - 1,true);
#endif

	printf("Try call mode\n");
	//	vManager.Mode(b.getData());
	//	CryptoPP::Integer * a1 = new CryptoPP::Integer(as);
	//	CryptoPP::Integer * b1 = new CryptoPP::Integer(bs);
	//	CryptoPP::Integer * c1 = new CryptoPP::Integer(cs);

	memset(buf,0,512);
	memcpy(buf,a -> getData(),128);

	time3 = clock();
	time1 = curtime();

	//		*a1 *= *a1;
	//	for(int e = 0 ; e < 10; e ++) {
	if (key_flag == 1) {
		//		printf("Generate first.\n");
		//		vManager.Mul(*a,*b);
		//		cout << "Number a*b: " << *a << endl;
		//		printf("----------- operation 1 ------------\n");
		vManager.exp(*a,*b);//a = a^b mod c
		//		printf("----------- operation 2 ------------\n");
		//		vManager.exp(*a,*b1);//a = a^b mod c
	} else {
		//		printf("Generate second.\n");
		//		vManager.Mul(*b,*a);
		//		cout << "Number b*a: " << *b << endl;
		//		printf("----------- operation 1 ------------\n");
		//		vManager.exp(*a,*b1);//a = a^b mod c
		//		printf("----------- operation 2 ------------\n");
		//		vManager.exp(*a,*b);//a = a^b mod c	
	}
	//		vManager.Mode((unsigned char *)buf);
	vManager.Mode2((unsigned char *)buf);
	//		*a1 = a_exp_b_mod_c(*a1,*b1,*c1);
	//		vManager.Mul(*a,*a);
	//	}
	time2 = curtime();
	time4 = clock();
	printf("time1: %lld\n",time1);
	printf("time2: %lld\n",time2);

	printf("Time of execution: %lld time: %ld\n",time2 - time1,time4 - time3);

	printf("Result of mode:\n");
	for(int i = 0; i < 40; i ++) if (buf[i] > 0xf) printf("%x:",buf[i]); else printf("0%x:",buf[i]);
	printf("\n");

	//	cout << "Result of a^b mod c: " << endl << *a << endl;
	//	cout << "Result CryptoPP: \n" << *a1 << endl;
	delete a;
	delete b;
	return 0;
}

inline long long curtime(void) {
	asm("rdtsc");
}

#endif
